Masala #1205

Qorbobo sizga juda injiq bola uchun sovg'a tayyorlashni buyurdi. Bola sovg'a sifatida ko'pi bilan $N$ ta shar olishni xohlaydi, lekin u injiqligi tufayli hamma sharlari och rangli bo'lib qolishini xohlamaydi, xuddi shunday to'q rangli bo'lib qolishini ham xohlamaydi. Sizga Qorbobo $K$ xil rangdagi sharlarning har biridan cheksiz miqdorda ishlatishga ruxsat berdi. Siz sovg'a bolaga yoqishi uchun quyidagicha usulda sovg'ani tayyorlashingiz kerak:

• $K$ xil shardan 1 tadan $N$ tagacha qilib yasash mumkin bo'lgan barcha turli sharlar to'plamini yasab chiqasiz va ularni och ranglardan to'qga qarab saralaysiz. (Leksikografik saralashga o'xshash, aniqroq tushunish uchun namunaviy test va uning izohini tekshiring)
• Tasavvur qiling sizda $S$ ta sovg'a (sharlar to'plami) hosil bo'ldi. Siz bolaga sovg'a sifatida $\frac{S}{2}$ - sovg'ani berasiz, chunki bu sovg'a ranglar jihatidan muvozanatlangan bo'ladi.

Bolaga berilgan sovg'adagi sharlar ranglarini chiqaring.

E'tibor bering: To'plamda bir nechta bir xil rangdagi sharlar bo'lishi mumkin.

$N$ va $K$ natural sonlari: $1 \leq N, K \leq 3*10^5$

Masala javobini chiqarishda ranglarni sonlar bilan ifodalang. Bunda 1 soni eng och rangga, $K$ soni eng to'q rangga mos keladi.